package zuoshen_video;

import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;
public class BottleSort {

    //1.利用计数排序得到排序后相邻两个元素之间的最大差值。
    public int findMaxCut1(int[] nums) {
        Map<Integer, Integer> map = new TreeMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }
        int last = -1, max = 0;
        for (int i: map.keySet()) {
            if (last == -1) last = i;
            else {
                max =  Math.max(i - last, max);
                last = i;
            }
        } 
        return max;
    }

    //1.利用半个桶排序得到最大差值
    public int findMaxCut(int[] nums) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE, res = 0, len = nums.length;
        for (int i = 0; i < nums.length; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }

        if (max == min) return 0;

        //定义桶
        boolean[] hasNumbers = new boolean[len + 1];
        int[] maxium = new int[len + 1], minium = new int[len + 1];
        int idx, lastMax;
        for (int i = 0; i < len; i++) {
            idx = (int)((nums[i] - min) * len / (max - min)); //计算当前元素应该存放的桶下标  桶排序最关键代码
            //先更新maxium和minium，根据之前有没有值进行覆盖或者直接添加
            maxium[idx] = hasNumbers[idx] ? Math.max(maxium[idx], nums[i]) : nums[i]; 
            minium[idx] = hasNumbers[idx] ? Math.min(minium[idx], nums[i]) : nums[i];
            hasNumbers[idx] = true;
        }


        lastMax = maxium[0]; //因为范围是从min到max，因此必定有值
        for (int i = 1; i < hasNumbers.length; i++) {
            if (hasNumbers[i]) {
                res = Math.max(minium[i] - lastMax, res);
                lastMax = maxium[i];
            }
        }
        return res;
    }

    @Test
    public void test2() {
        int[] nums = ArrayGenerator.getArray(100, 10);
        nums = new int[]{98, 66, 80, 74, 94, 64, 90, 30, 28, 50};
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums));
        System.out.println(rightFindMaxCut(nums));
        System.out.println(findMaxCut(nums));
    }

    public int rightFindMaxCut(int[] nums) {
        Arrays.sort(nums);
        int max = 0;
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(max, nums[i] - nums[i - 1]);
        }
        return max;
    }


    @Test
    public void test() {
        for (int i = 0; i < 1000; i++) {
            int[] nums = ArrayGenerator.getArray(100, 10);
            if (findMaxCut(nums) != rightFindMaxCut(nums)) {
                System.out.println("fucked");
            }
        }
        System.out.println("nice");
    }
}
